import java.util.List;

public class MySingleList {
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }
    public ListNode head;

    public void createLink(){
        ListNode listNode1=new ListNode(1);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(3);
        ListNode listNode4=new ListNode(4);
        ListNode listNode5=new ListNode(5);
        ListNode listNode6=new ListNode(6);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        listNode5.next=listNode6;
        head=listNode1;
    }


//    1.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
    public ListNode partition(int x) {
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;
        ListNode cur=head;
        while (cur!=null){
            if(cur.val<x){
                if(bs==null){
                    bs=cur;
                    be=cur;
                }else{
                    be.next=cur;
                    be=be.next;
                }
            }else{
                if(as==null){
                    as=cur;
                    ae=cur;
                }else{
                    as.next=cur;
                    ae=ae.next;
                }
            }
            cur=cur.next;
        }
        if(bs==null){
            return as;
        }
        be.next=as;
        if(as!=null){
            ae.next=null;
        }
        return bs;
    }


//    2. 输入两个链表，找出它们的第一个公共结点 。
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null&&headB==null){
            return null;
        }

        int len1=0;
        int len2=0;
        ListNode pl=headA;
        ListNode ps=headB;
        while (pl!=null){
            len1++;
            pl=pl.next;
        }
        while (ps!=null){
            len2++;
            ps=ps.next;
        }
        pl=headA;
        ps=headB;
        int len=len1-len2;
        if(len<0){
            pl=headB;
            ps=headA;
            len=len2-len1;
        }
        while (len!=0){
            pl=pl.next;
            len--;
        }
        while(pl!=ps){
            pl=pl.next;
            ps=ps.next;
        }
        return pl;
    }


//    3. 给定一个链表，判断链表中是否有环 。
    public boolean hasCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }


//    4. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }
        if(fast==null||fast.next==null){
            return null;
        }
        slow=head;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }


}



